package basic.study.leetcode;

import java.util.ArrayDeque;

/**
 * @ClassName Hard239
 * @Description 滑动窗口的最大值
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/9 11:04
 * @Version 1.0
 */
public class Hard239 {
    class Solution {
        ArrayDeque<Integer> deq = new ArrayDeque<>();
        int[] nums;

        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            if (n * k == 0) return nums;
            if (k == 1) return nums;

            this.nums = nums;
            int[] output = new int[n - k + 1];

            //初始化
            int maxId = 0;
            for (int i = 0; i < k; i++) {
                cleanDeq(i, k);
                deq.addLast(i);
                if (nums[i] > nums[maxId]) maxId = i;
            }
            output[0] = nums[maxId];

            //滑动
            for (int i = k; i < nums.length; i++) {
                cleanDeq(i, k);
                deq.addLast(i);
                output[i - k + 1] = nums[deq.getFirst()];
            }
            return output;
        }

        private void cleanDeq(int i, int k) {
            //先清除过期的
            while (!deq.isEmpty() && deq.getFirst() == i - k) {
                deq.removeFirst();
            }
            //在清除比当前值小的
            while (!deq.isEmpty() && nums[deq.getLast()] < nums[i]) {
                deq.removeLast();
            }
        }
    }

}
